package com.zp.self.module.level_4_算法练习.算法.排序;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author By ZengPeng
 */
public class X_基数排序_O_nXk {
    @Test
    public void main() {
        int[] arr = {23237, 11, 5, 311, 623, 4231};
        new X_基数排序_O_nXk().baseSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     题目：基数排序
     案例：字符串的基数排序

     分析：
         基数排序：时间：O(n*k) k==最大位长度 、空间：O(n+10)、顺序稳定
         概述：属于关键字排序【高位优先、低位优先】，
             低位优先：先遍历arr元素的最后一位，进行计算排序。然后比较上一位，依次向前推进
             高位优先：找出第一位相同的桶，递归每一个位相同的桶，属于分治法的一种
         实现：
             1.创建计数数组count: 记录每一位的个数。 temp临时数组：用于每一次排序时交换整个数组
             2.遍历arr:找到最大值，得到他的长度h: 不断/10 是商否为0
             3.双重循环遍历h、arr: 不断除以division = (10*h++)   然后将其放入对应的桶count[%10]++
             4.利用计数排序的方式：遍历arr,将数组迁移到temp; 然后重新赋值给arr
             5.跳出外层 h 循环后：temp已经将数组复制给了arr,返回arr即可

            *负数的兼容：扩展count 长度为20即可，前面10个存负数
     **/
    public void baseSort(int[] arr) {
        //1.创建计数数组count: 记录每一位的个数。 temp临时数组：用于每一次排序时交换整个数组
        int[] count = new int[10], temp = new int[arr.length];
        // 2.遍历arr:找到最大值，得到他的长度h: 不断/10 是商否为0
        int max=0,h=0,arrLength=arr.length;
        for (int num : arr) max= Math.max(max,num);
        while (max!=0){
            max=max/10;
            h++;
        }
        //3.双重循环遍历h、arr: 不断除以division = (10*h++)   然后将其放入对应的桶count[%10]++
        for (int i = 0; i < h; i++) {
            int division = (int)Math.pow(10,i);
            for (int anArr : arr)
                count[anArr / division % 10]++;
            //4.利用计数排序的方式：遍历arr,将数组迁移到temp; 然后重新赋值给arr
            for (int j = 1; j < 10; j++)
                count[j] +=count[j-1] ;
            for (int index = arrLength-1; index>=0; index--) {
                temp[--count[arr[index] / division % 10]] = arr[index];
            }
            Arrays.fill(count,0);
            System.arraycopy(temp,0,arr,0,arrLength);
        }
        //5.跳出外层 h 循环后：temp已经将数组复制给了arr,返回arr即可
    }
}